#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;

void nextPermutation(vector<int>& nums) 
{
  int m = nums.size();
  if( m<2 )
    return;

  for(int i=m-1;i>0;--i)
  {
    int j=i-1;
    int stopValue = -1;

    if( nums[i] > nums[j] )
    {
      stopValue = nums[i];

      int k = i;
      for( int ik=i; ik<m; ++ik )
      {
        if( nums[ik]<stopValue && nums[ik]>nums[j] )
        {
          stopValue = nums[ik];
          k = ik;
        }
      }

      int tmp = nums[j];
      nums[j] = nums[k];
      nums[k] = tmp;

      std::sort( nums.begin()+i, nums.end() );

      return;

    }

  }

  std::sort( nums.begin(), nums.end() );

}




int main(int argc,char *argv[])
{

  vector<int> nums={4,2,0,2,3,2,0};
  vector<int> nums1={3,2};
  vector<int> nums2={1,1,5};




  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  //func();
  nextPermutation(nums);


  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;

  for(auto iter = nums.begin();iter!=nums.end();++iter)
    cout<<*iter<<",";
  cout<<endl;



  return 0;
}
